package workexp.alg.sword.tree;

import workexp.alg.env.TreeNode;

public class ReConstructBinaryTree {

    public TreeNode reConstructBinaryTree(int[] pre, int[] mid){
        TreeNode root = null;
        if(pre==null||pre.length==0||mid==null||mid.length==0){
            return root;
        }
        root = constructBinaryTree(pre,0,pre.length-1,mid,0,mid.length-1);
        return root;

    }

    public TreeNode constructBinaryTree(int[] pre,int prestart,int preend,int[] mid,int midstart,int midend){
        TreeNode root =null;
        if(prestart>preend||midstart>midend){
            return root;
        }
        root = new TreeNode(pre[prestart]);
        for(int index = prestart;index<=preend;index++){
            //prestart+index-midstart 前序起始点加上 中序左子树元数数目（index-midstart）
            root.left=constructBinaryTree(pre,prestart+1,prestart+index-midstart,mid,midstart,index-1);

            root.right=constructBinaryTree(pre,prestart+index-midstart+1,preend,mid,index+1,midend);
            break;
        }
        return root;

    }
}
